package tianhao.luo.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: tianhao.luo@hand-china.com 2021/6/27  下午5:24
 */
public class Graph {

    /**
     * 存储顶点集合
     */
    private List<String> vertexList;

    /**
     * 存储图对应的邻接矩阵
     */
    private int[][] edges;

    /**
     * 表示边的数目
     */
    private int numOfEdges;

    /**
     * 记录结点是否被访问
     */
    private boolean[] isVisited;


    public Graph(int n) {
        // 初始化邻接矩阵
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        isVisited = new boolean[n];
    }

    // 插入结点
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 插入边
     * @param v1 表示点的下标
     * @param v2 表示点的下标
     * @param weight 是否联通,1通,0不通
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }


    /**
     *
     * @return 结点个数
     */
    public int getNumOfVertex(){
        return vertexList.size();
    }

    /**
     *
     * @return 边的个数
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }


    /**
     *
     * @param i
     * @return 返回结点i对应的数据 0->A 1->B
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    /**
     *
     * @param v1 表示点的下标
     * @param v2 表示点的下标
     * @return 获取通路
     */
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    public void showGraph(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }



    /**
     * 得到第一个邻接节点的下标w
     * @param index 索引
     * @return 索引
     */
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertexList.size(); i++) {
            // 找出第一个联通的结点
            if (edges[index][i] > 0){
                return i;
            }
        }
        return -1;
    }

    /**
     * 如果结点被访问过,则需要跳过结点,去找下一个结点
     * 根据结点的第一个一个邻接节点的下标来获取第二个邻接节点
     * @param v1 前一个邻接节点的下表
     * @param v2
     * @return
     */
    public int getNextNeighbor(int v1,int v2){
        for (int i = v2 +1; i < vertexList.size(); i++) {
            // v1到下一个结点存在通路
            if (edges[v1][i] > 0){
                return i;
            }
        }
        return -1;
    }

    /**
     * 深度优先遍历
     * 1. i第一次就是0
     */
    private void dfs(int i){
        System.out.print(getValueByIndex(i)+ "->");
        // 将结点设置为已访问
        isVisited[i] =true;

        // 查找结点i的第一个邻接节点w
        int w = getFirstNeighbor(i);
        while (w != -1){
            if (!isVisited[w]){
                dfs(w);
            }
            // 如果w结点已经被访问过,则跳过该结点,找下一个
            w = getNextNeighbor(i,w);
        }
    }

    /**
     * 1. 访问初始结点v，并标记结点v为已访问。
     * 2. 查找结点v的第一个邻接结点w。
     * 3. 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
     * 4. 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
     * 5. 若w被访问过，查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
     *
     * 代表其中第三步中的,回到第一步,从下一个结点继续
     * 遍历所有的结点,并进行dfs
     */
    public void dfs(){
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]){
                dfs(i);
            }
        }
    }


    //广度优先

    private void bfs(int i){
        // 表示队列的头结点的下标
        int u;
        // 邻接节点的下表w
        int w;

        // 队列,记录结点访问的顺序
        LinkedList<Integer> queue = new LinkedList<>();
        // 访问结点
        System.out.print(getValueByIndex(i)+"=>");
        // 标记为已访问
        isVisited[i] = true;
        // 将结点加入尾部
        queue.addLast(i);

        while (!queue.isEmpty()){
            // 取出队列的头结点下标
            u = queue.removeFirst();
            // 的到第一个邻接节点的下标
            w =getFirstNeighbor(u);
            while (w != -1){
                if (!isVisited[w]){
                    // 输出
                    System.out.print(getValueByIndex(w)+"=>");
                    // 记录已访问
                    isVisited[w] = true;
                    // 入队列
                    queue.addLast(w);
                }else {
                    // 访问过了, 以u为起点,找下一个结点
                    // 体现出广度优先
                    w = getNextNeighbor(u,w);
                }
            }
        }
    }

    // 遍历所有结点,进行广度优先搜索

    public void bfs(){
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]){
                bfs(i);
            }
        }
    }
}
